A methodology for determining amino-acid substitution matrices from set covers

摘要

We introduce a new methodology for the determination of amino-acidsubstitution matrices for use in the alignment of proteins. The new methodologyis based on a pre-existing set cover on the set of residues and on theundirected graph that describes residue exchangeability given the set cover.For fixed functional forms indicating how to obtain edge weights from the setcover and, after that, substitution-matrix elements from weighted distances onthe graph, the resulting substitution matrix can be checked for performanceagainst some known set of reference alignments and for given gap costs. Findingthe appropriate functional forms and gap costs can then be formulated as anoptimization problem that seeks to maximize the performance of the substitutionmatrix on the reference alignment set. We give computational results on theBAliBASE suite using a genetic algorithm for optimization. Our results indicatethat it is possible to obtain substitution matrices whose performance is eithercomparable to or surpasses that of several others, depending on the particularscenario under consideration.